package com.example.leetcode.sort;

import java.util.Arrays;

/**
 * @ClassName MergeSort
 * @Description 归并排序
 *     思路: https://www.runoob.com/w3cnote/implementation-of-merge-sort.html
 *
 * @Author liuzhihui
 * @Date 21/4/2021 下午 11:41
 * @Version 1.0
 **/
public class MergeSort {
    public static void main(String[] args) {
        int arr[]={3, 9, -1, 10, -2};
        System.out.println("排序前：" + Arrays.toString(arr));
        mergeSort1(arr,0,arr.length - 1,new int[arr.length]);
        System.out.println("排序后：" + Arrays.toString(arr));
    }

    private static void mergeSort(int[] arr, int first, int last, int[] temp){
        if(first < last){
            int mid = (first + last) / 2;
            // 左边有序
            mergeSort(arr,first,mid,temp);
            // 右边有序
            mergeSort(arr,mid + 1, last, temp);
            //再将二个有序数列合并
            mergeArr(arr, first, mid, last, temp);
        }
    }
    private static void mergeArr(int[] arr, int first, int mid, int last, int[] temp){
        int f = first;
        int l = last;
        int m = mid;
        int t = 0;
        int j = mid +1;

        // 左指针小于等于中值且中值+1小于右指针时
        while(f <= m && j <= l){
            // 左指针对应的值小于右区间的第一个数时
            if (arr[f] < arr[j]){
                //将小的数放到临时数组中
                temp[t] = arr[f];
                t++;
                f++;
            }else {
                temp[t] = arr[j];
                t++;
                j++;
            }
        }
        // 右区间的元素都加到临时数组中了，但是左区间还有元素没有放到数组中
        while(f <= m){
            temp[t] = arr[f];
            t++;
            f++;
        }
        // 左区间的元素都加到临时数组中，但是在右区间还有元素没有放到数组中
        while(j <= l){
            temp[t] = arr[j];
            t++;
            j++;
        }
        // 将temp中的元素重新赋回arr数组中
        for (int i = 0; i < t; i++) {
            arr[first + i] = temp[i];
        }
    }

    //练习
    private static void mergeSort1(int[] arr, int first, int last, int[] temp){
        if (first < last){
            int mid = (first + last) / 2;
            //向左区间排序
            mergeSort1(arr, first, mid, temp);
            //向右区间排序
            mergeSort1(arr, mid + 1, last, temp);
            //将两个有序的数组合并
            mergeArray(arr,first, mid,last,temp);
        }
    }
    // 将一个数组，分为两半，两个组数一起遍历，比较，小的值就放到一个数组中
    private static void mergeArray(int[] arr, int left ,int mid, int right ,int temp[]){
        int l = left;
        int m = mid;
        int j = mid + 1;
        int r = right;
        int tempIndex = 0;

        while(l <= m && j <= r){
            if (arr[l] < arr[j]){
                temp[tempIndex++] = arr[l++];
            }else{
                temp[tempIndex++] = arr[j++];
            }
        }
        // 循环结束，左区间还有元素，右区间已经没元素了
        while(l <= m){
            temp[tempIndex++] = arr[l++];
        }
        while(j <= r){
            temp[tempIndex++] = arr[j++];
        }
        for (int i = 0; i < tempIndex; i++) {
            // todo 注意这里，经常忘记加left
            arr[left + i] = temp[i];
        }
    }

}
